Rectangular tileability and complementary tileability are undecidable

摘要

Does a given a set of polyominoes tile some rectangle? We show that thisproblem is undecidable. In a different direction, we also consider tiling acofinite subset of the plane. The tileability is undecidable for many variantsof this problem. However, we present an algorithm for testing whether thecomplement of a finite region is tileable by a set of rectangles.